package recursion;

import java.util.Scanner;

public class FeiBoNaQi2 {
    public static void main(String[] args) {
        while (true) {
            System.out.print("输入整数n，求第n个斐波那契数：");
            int n = new Scanner(System.in).nextInt();
            long result = f(n);
            System.out.printf("第%d个斐波那契数是：%d\n", n, result);
        }
    }

    private static long f(int n) {
        /*

        1   1   2   3
                a   b

        b = a+b;
        a = b-a;
         */

        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        long a=1;
        long b=1;
        for (int i = 3; i <= n; i++) {
            b = a+b;
            a = b-a;
        }
        return b;
    }
}
